//LCR 116.省份数量
//https://leetcode.cn/problems/bLyHh0/
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int> ufs(n,-1); //并查集

        function<int(int)> FindRoot = [&ufs](int s){
            while(ufs[s] >= 0) s = ufs[s];
            return s;
        };

        //将相连的城市添加到一个集合中
        for(int i = 0;i<n;++i)
            for(int k = 0;k<n;++k)
                if(isConnected[i][k] == 1)
                {
                    //加入一个集合中
                    int root1 = FindRoot(i);
                    int root2 = FindRoot(k);
                    if(root1 == root2) continue; //如果两个根相同则不处理
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }

        int ret = 0;
        for(int i = 0;i<n;++i) ret+=(ufs[i]<0);
        return ret;
    }
};